package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
 */
public class _0_剑指Offer22_链表中倒数第k个节点 {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null || k < 0) return null;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            k--;
        }

        if (k == 0) {
            // 倒数第k个节点是头节点
            return head;
        }

        if (k < 0) {
            // 倒数第k个节点在链表内部。再从头往后遍历，直到k=0，此时得到的节点是倒数第k个节点的前一个节点
            cur = head;
            while (++k != 0) {
                cur = cur.next;
            }
            // 此时的cur是倒数第k个节点的前一个节点
            return cur.next;
        }

        return null;
    }
}
